package search.binarysearch;

public class CutWood {

    public static void main(String[] args) {
        int[] nums = {612, 301, 257, 900};
        System.out.println(new CutWood().cutWood(nums, 10));
    }

    /**
     * 二分法的思想：先拿最大木头来分
     * <p>
     * 将一堆木头切成指定的块数，求出单块木头最大长度
     *
     * @param nums 木头集合
     * @param k    块数
     * @return 单块木头最大长度
     */
    public int cutWood(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int start = 1;
        int end = getMax(nums);
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            int pieces = getPieces(nums, mid);
            //能够切分，但不一定是单个最长的木头
            if (pieces > k) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (getPieces(nums, start) >= k) {
            return start;
        }
        if (getPieces(nums, end) >= k) {
            return end;
        }
        return 0;
    }

    /**
     * 获取能切多少块
     *
     * @param nums 木块集合
     * @param mid  每块大小
     * @return 块数
     */
    private int getPieces(int[] nums, int mid) {

        int pieces = 0;
        for (int num : nums) {
            pieces += num / mid;
        }
        return pieces;
    }

    /**
     * 获取木材中最大长度
     *
     * @param nums 木材集合
     * @return 最大值
     */
    private int getMax(int[] nums) {
        int max = 0;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}
